package com.yangzhe.algorithm.c024;

/**
 * 测试链接 : https://leetcode.cn/problems/kth-largest-element-in-an-array/
 * 题目要求 时间复杂度 O(n)
 * 使用随机快排。每一轮partition会使得随机数x的位置确定，此时：
 * 	1. 发现kIndex在 =x 范围内，则代表是答案
 * 	2. 发现kIndex 在 <x 范围内，则继续在 l 至 smallBorder范围内partition，不用管largerBorder 至 r范围
 * 	3. 发现kIndex 在 >x 范围内，则继续在 largerBorder 至 r范围partition，不用管l 至 smallBorder范围
 * 最坏情况，每次随机都只能搞定最后一个数，n - 1, n - 2, n - 3, ... 1，需要遍历 n + (n - 1) + (n - 2) + ... + 1 = n ^ 2。复杂度O(n ^ 2)
 * 最好情况，每次都能随机到中间位置，遍历 n + n/2 + n/4 + n/8 + ... + 1 = 2n - 1，等比数列。复杂度O(n)
 *
 * 但是由于随机因素，所以这里计算的是期望值，证明在算法导论-9.2最终复杂度就是O(n)
 */
class RandomizedSelect {

	public static void main(String[] args) {
		// 生成测试用例
		int[] nums = {3,2,1,5,6,4};
		// 调用方法
		RandomizedSelect randomizedSelect = new RandomizedSelect();
		System.out.println(randomizedSelect.findKthLargest(nums, 2));
	}

	public int smallBorder;
	public int largerBorder;


	public int findKthLargest(int[] nums, int k) {
		// 第k大，相当于从排序的数组中倒数第k个，数组排序后，返回kIndex位置的元素即可
		int kIndex = nums.length - k;

		// 使用随机快排。每一轮partition会使得随机数x的位置确定，此时：
		// 1. 发现kIndex在 =x 范围内，则代表是答案直接返回
		// 2. 发现kIndex 在 <x 范围内，则继续在 l 至 smallBorder范围内partition，不用管largerBorder 至 r范围
		// 3. 发现kIndex 在 >x 范围内，则继续在 largerBorder 至 r范围partition，不用管l 至 smallBorder范围
		int l = 0;
		int r = nums.length - 1;
		while (l <= r) {
			int x = nums[l + (int)(Math.random() * (r - l + 1))];
			partition(nums, l, r, x);
			if (kIndex >= smallBorder && kIndex <= largerBorder) {
				return nums[kIndex];
			} else if (kIndex < smallBorder) {
				r = smallBorder - 1;
			} else {
				l = largerBorder + 1;
			}
		}

		return -1;
	}

	/**
	 * 荷兰国旗问题
	 * 将数组分别分成 <x =x >x
	 */
	public void partition(int[] nums, int l, int r, int x) {
		// 数组中等于x位于 smallBorder和largerBorder之间
		// 数组中小于x的边界
		int smallBorder = l;
		// 数组中大于x的边界
		int largerBorder = r;

		// 从l开始遍历数组
		int i = l;
		while(i <= largerBorder) {
			if (nums[i] == x) {
				i++;
			} else if (nums[i] < x) {
				swap(nums, i++, smallBorder++);
			} else {
				swap(nums, i, largerBorder--);
			}
		}

		this.smallBorder = smallBorder;
		this.largerBorder = largerBorder;
	}

	public void swap(int[] nums, int a, int b) {
		int temp = nums[a];
		nums[a] = nums[b];
		nums[b] = temp;
	}
}